package com.zjsru.plan2023.oneday;

import java.util.Arrays;

/**
 * @Author: cookLee
 * @Date: 2023-12-19
 * 寻找峰值 II
 */
public class FindPeakGrid {

    /**
     * 主
     * \
     * 输入: mat = [[1,4],[3,2]]
     * 输出: [0,1]
     * 解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。
     * \
     * 输入: mat = [[10,20,15],[21,30,14],[7,16,32]]
     * 输出: [1,1]
     * 解释: 30 和 32 都是峰值，所以[1,1]和[2,2]都是可接受的答案。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindPeakGrid findPeakGrid = new FindPeakGrid();
        int[][] mat = new int[][]{{1, 4}, {3, 2}};
        System.out.println(Arrays.toString(findPeakGrid.findPeakGrid(mat)));
    }

    /**
     * 查找峰值网格
     * 暴力遍历
     * @param mat 垫子
     * @return {@link int[]}
     */
    public int[] findPeakGrid(int[][] mat) {
        int rowLen = mat.length;
        int colLen = mat[0].length;
        int first = 0;
        int second = 0;
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                //只要获取最高点，那一定是峰值
                if(mat[i][j] > mat[first][second]){
                    first = i;
                    second = j;
                }
            }
        }
        return new int[]{first,second};
    }

    /**
     * 二分法
     *
     * @param mat 垫子
     * @return {@link int[]}
     */
    public int[] findPeakGrid2(int[][] mat) {
        int rowLen = mat.length;
        int colLen = mat[0].length;
        int low = 0, high = rowLen - 1;
        //通过二分找到中间行，每行的最高值来判断获取峰值
        while (low <= high) {
            //定义i为中间行
            int i = (high + low) / 2;
            int j = -1, max = -1;
            for (int k = 0; k < colLen; k++) {
                if (mat[i][k] > max) {
                    //获取最大值的下标
                    j = k;
                    //获取最大值
                    max = mat[i][k];
                }
            }
            //如果当前行的元素小于上一行相同列的元素，说明峰值在当前行上方，更新 high 为 i - 1
            if (i - 1 >= 0 && mat[i][j] < mat[i - 1][j]) {
                high = i - 1;
                continue;
            }
            //如果当前行的元素小于下一行相同列的元素，说明峰值在当前行下方，更新 low 为 i + 1。
            if (i + 1 < rowLen && mat[i][j] < mat[i + 1][j]) {
                low = i + 1;
                continue;
            }
            return new int[]{i, j};
        }
        //不存在峰值的情况
        return new int[0];
    }

}
